---
title: "凑平方数"
created: 2025-11-28
tags:
  - 算法
---

# 凑平方数

## 题目 [凑平方数](https://www.lanqiao.cn/paper/3863/problem/653/)

![[image-3a1b714e.png]]

## 思路分析

![[image-da9db519.png]]

这样不是很好暴力 ……

有个想法 能不能从平方数入手

既然预处理出来了所有的平方数 那试着把这些所有的平方数进行排列组合 最后如果满足0~9的所有数最多出现一次 就算一种合法方案？

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	for(LL i=1;i*i<9876543210LL;i++){
		cout<<i*i<<endl;

	}
	return 0;
 }
```

终端不会显示全部的输出（当输出过多时） 可以用下列命令将输出放入txt文件 进行检查

`C:\code\c++\lanqiao>7th.exe > output.txt`

![[2-Learning/02-算法/04-冲刺国赛/国赛真题/第七届蓝桥杯大赛软件赛决赛C-C++ 大学 B 组/assets/image-e7ce63c5.png]]

数全提出来了 排列组合 dfs

……

程序没有输出并且返回了错误码 3221225725（在 Windows 环境中，这通常是因为访问违规或内存溢出导致的崩溃），这意味着可能存在几个问题。一是可能是代码中存在逻辑错误或效率问题导致内存消耗过大，二是可能是递归过深导致栈溢出。

爆系统栈了……

得想办法优化

首先 这些数不全是合法的 比如 100是个平方数 但就它本身而言 0就出现了两次 显然不满足 所以可以提前把这些数筛掉

其次 组合时 只需要单纯检查长度为10的字符串是否0~9只出现一次 无须考虑什么逗号

若长度大于10 或者 发现组合后不满足每个数只出现一次 就可以直接剪枝

只有长度恰好为10 且每数只出现一次的字符串才是合法方案

一个还算比较常规的dfs吧

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
vector<LL> alls;
LL N,ans;

bool check(string s){
	int vis[10]={0};
	for(char c:s){
		int t=c-'0';
		vis[t]++;
		if(vis[t]>1)
			return false;
	}
	return true;
}

void dfs(int st,string num){
	int len=num.length();
	if(len>10 || !check(num))
		return;
	if(len==10 && check(num)){
		ans++;
		return;
	}
	for(int i=st;i<N;i++)
		dfs(i+1,num+to_string(alls[i]));
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(LL i=0;i*i<9876543210LL;i++){
		LL tmp=i*i;
		if(check(to_string(tmp)))
			alls.push_back(tmp);
	}
	N=alls.size();
	dfs(0,"");
	cout<<ans<<endl;
	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[一步之遥|一步之遥]] 🏠 [[00-冲刺国赛]] ➡️ [[棋子换位|棋子换位]]